package com.leetcode.partition3;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/11/6 9:40
 */
public class LC268丢失的数字 {

    public static int missingNumber(int[] nums) {
        return math(nums);
    }

    public static void main(String[] args) {
        int[] nums = {3, 0, 1};
        System.out.println(missingNumber(nums));
    }

    private static int math(int[] nums) {
        //首项为1，公差为1，求前n项和，sum就是本该正常的序列和
        int n = nums.length;
        int sum = n + n * (n - 1) / 2;
        for (int i = 0; i < nums.length; i++) {
            sum -= nums[i];
        }
        return sum;
    }

    private static int bitManipulation(int[] nums) {
        int answer = 0;
        //异或运算，只有没有出现的数字会被找到。比如 [1, 0, 3] -> 0 ^ 1 ^ 1 ^ 2 ^ 0 ^ 3 ^ 3，相同的抵消为0，只剩下没有出现的
        for (int i = 0; i < nums.length; i++) {
            answer ^= nums[i];
            answer ^= i + 1;
        }
        return answer;
    }

    private static int hashtable(int[] nums) {
        int[] count = new int[nums.length + 1];
        for (int num : nums) {
            count[num] = 1;
        }
        System.out.println(Arrays.toString(count));
        for (int i = 0; i <= nums.length; i++) {
            if (count[i] != 1) {
                return i;
            }
        }
        return -1;
    }
}
